Toroidal graphs containing neither $K_5^{-}$ nor 6-cycles are 4-choosable

摘要

The choosability $\chi_\ell(G)$ of a graph $G$ is the minimum $k$ such thathaving $k$ colors available at each vertex guarantees a proper coloring. Givena toroidal graph $G$, it is known that $\chi_\ell(G)\leq 7$, and$\chi_\ell(G)=7$ if and only if $G$ contains $K_7$. Cai, Wang, and Zhu provedthat a toroidal graph $G$ without 7-cycles is 6-choosable, and $\chi_\ell(G)=6$if and only if $G$ contains $K_6$. They also prove that a toroidal graph $G$without 6-cycles is 5-choosable, and conjecture that $\chi_\ell(G)=5$ if andonly if $G$ contains $K_5$. We disprove this conjecture by constructing aninfinite family of non-4-colorable toroidal graphs with neither $K_5$ norcycles of length at least 6; moreover, this family of graphs is embeddable onevery surface except the plane and the projective plane. Instead, we prove thefollowing slightly weaker statement suggested by Zhu: toroidal graphscontaining neither $K^-_5$ (a $K_5$ missing one edge) nor 6-cycles are4-choosable. This is sharp in the sense that forbidding only one of the twostructures does not ensure that the graph is 4-choosable.